// class Solution {
//     public int waysToStep(int n) {
//         if (n == 1 || n == 2) {
//             return n;
//         }
//         if (n == 3) {
//             return 4;
//         }
//         int[] dp = new int[n+1];
//         dp[1] = 1;
//         dp[2] = 2;
//         dp[3] = 4;
//         for (int i = 4; i <= n; i++) {
//             dp[i] = (dp[i-1]+(dp[i-2]+dp[i-3])%1000000007)%1000000007;
//         }
//         return dp[n];
//     }
// }


class Solution {
    public int waysToStep(int n) {
        if (n == 1 || n == 2) {
            return n;
        }
        if (n == 3) {
            return 4;
        }
        int a = 1, b = 2, c = 4;
        for (int i = 4; i <= n; i++) {
            int sum = (a+((b+c)%1000000007))%1000000007;
            a = b;
            b = c;
            c = sum;
        }
        return c;
    }
}